//
//  1.二维数组查找.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/5/17.
//

import Foundation
/*
 题目：在⼀个⼆维数组中，每⼀⾏都按照从左到右递增的顺序排序，每⼀列都按照从上到下递增的顺序排序。请完成⼀个函数，输⼊这样的⼀个⼆维数组和⼀个整数，判断数组中是否含有该整数。
 思路：⾸先选取数组中右上⻆的数字。如果该数字等于要查找的数字，查找过程结束；如果该数字⼤于要查找的数组，剔除这个数字所在的列；如果该数字⼩于要查找的数字，剔除这个数字所在的⾏。也就是说如果要查找的数字不在数组的右上⻆，则每⼀次都在数组的查找范围中剔除⼀⾏或者⼀列，这样每⼀步都可以缩⼩查找的范围，直到找到要查找的数字，或者查找范围为空
 */
func offer_1() {
    print(twoDimensionalArrayLookup(array: [[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]], target: 7))
}

fileprivate func twoDimensionalArrayLookup(array: [[Int]], target: Int) -> Bool {
    // 使用下标模拟删除，省内存
    guard ((array.last?.last) != nil) else { return false }
    var row = 0
    var col = array.first!.count - 1
    while row < array.count - 1 && col >= 0 {
        // 数组中右上⻆的数字
        let curNum = array[row][col]
        if curNum > target {
            // 删除列
            col -= 1
        } else if curNum < target {
            // 删除行
            row += 1
        } else {
            return true
        }
    }
    return false
}
